/*
 * @lc app=leetcode.cn id=1646 lang=java
 *
 * [1646] 获取生成数组中的最大值
 */

// @lc code=start
class Solution {
    //模拟题，暴力解即可
    public int getMaximumGenerated(int n) {
        int max = 0;//记录最大值
        int[] t = new int[n+1];//长度n+1的数组
        //注意上面写长度为n+1，如果n==0的时候t[1]是不能访问的。
        if(n<2) return n;
        t[0] = 0;t[1]=1;
        for(int i = 2 ;i<=n;i++){//长度n+1的数组，故第n个也要生成
            if(i%2==0){
                t[i] = t[i/2];
            }else{
                t[i] = t[i/2]+t[(i/2)+1];
            }
            max = Math.max(max, t[i]);
        }
        return max;
    }
}
// @lc code=end

